package com.atwulidun.dynamicprogramming03.knapsackproblem.unrefined;

import java.util.Arrays;

// 对于完全背包问题(未进行空间优化)：
// 问题描述：
// 一共有N种物品，每种物品有无限多个，第i（i从1开始）种物品的重量为w[i]，价值为v[i]。在总重量不超过背包承载上限W的情况下，能够装入背包的最大价值是多少？
// 分析一：
// 状态转移方程为：dp[i][j] = max(dp[i−1][j], dp[i][j−w[i]]+v[i])
// 分析二：
// 从装入第 i 种物品多少件出发，01背包只有两种情况即取0件和取1件，而这里是取0件、1件、2件...直到超过限重（k > j/w[i]），所以状态转移方程为：
// # k为装入第i种物品的件数, k <= j/w[i]
// dp[i][j] = max{(dp[i-1][j − k*w[i]] + k*v[i]) for every k}
public class UnboundedKnapsackProblem {
    // 物体的重量
    private static int[] w = {2, 4, 3};
    // 物体的价值
    private static int[] v = {500, 3000, 1000};
    // 背包的最大容量
    private static int maxWeight = 8;
    // 前i个物体能装入背包容量为j时的最大价值
    // 行代表第几个物体，列代表背包的容量
    private static int[][] dp = new int[w.length + 1][maxWeight + 1];
    // 记录背包装入的物体，与dp维度相同
    private static int[][] path = new int[w.length + 1][maxWeight + 1];


    public static void main(String[] args) {
        // 对dp进行初始化，第一行和第一列全为0
        // 第一行置为0
        Arrays.fill(dp[0], 0);
        // 第一列置为0
        for (int i = 0; i < dp.length; i++) {
            dp[i][0] = 0;
        }

        // 分析一：
        // 动态地将物品装入背包
        // 外层循环控制物体
        for (int i = 1; i < dp.length; i++) {
            // 内层循环控制背包容量
            for (int j = 1; j < dp[0].length ; j++) {
                // 如果当前物品的重量大于当前背包最大的容量
                // 注意：w的下标是从0开始，这里要减个1
                if (w[i - 1] > j) {
                    // 使用前i-1个物品的装入策略
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // 如果当前物品的重量小于等于当前背包的最大容量，这时要比较：
                    // 前i-1个物品的装入策略；装入当前物品，同时剩余空间再装前i个物品
                    // 注意：v的下标也是从0开始，故这里也要-1
                    if (dp[i - 1][j] < v[i - 1] + dp[i - 1][j - w[i - 1]]) {
                        dp[i][j] = v[i - 1] + dp[i][j - w[i - 1]];
                        // 同时把path对应当前的dp[i][j]标记为1
                        path[i][j] = 1;
                    } else {
                        dp[i][j] = dp[i - 1][j];
                    }
                }
            }
        }

        // 对dp进行逆向遍历
        int i = path.length - 1;// 表示最后一件物体
        int j = path[0].length - 1;// 表示背包的最大容量
        while (i > 0 && j > 0) {
            // 如果背包的最大容量装入的是最后一件物体
            // 注意：这里用while是因为最后一件物品有可能被重复放进背包
            while (path[i][j] == 1) {
                System.out.println("第" + i + "件物品装入背包");
                j -= w[i - 1];// 求出剩余的空间
            }
            // 这里分两种情况：
            // 1.如果上面的while成立，那么i--是看剩余的空间是否装入了前一件物品
            // 2.如果上面的while不成立，那么i--是看当前空间是否装入了前一件物品
            i--;
        }
        for (int[] ints : dp) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }
        for (int[] ints : path) {
            for (int anInt : ints) {
                System.out.print(anInt + " ");
            }
            System.out.println();
        }


//        // 分析二：
//        // 动态地将物品装入背包
//        // 第一层循环控制物体
//        for (int i = 1; i < dp.length; i++) {
//            // 第二层循环控制背包容量
//            for (int j = 1; j < dp[0].length ; j++) {
//                // k == 0时
//                int maxVal = dp[i - 1][j - 0 * w[i - 1]] + 0 * v[i - 1];
//                // maxVal对应的k
//                int maxK = 0;
//                // 第三层循环控制当前物体的数量
//                for (int k = 1; k <= j / w[i - 1]; k++) {
//                    if (dp[i - 1][j - k * w[i - 1]] + k * v[i - 1] > maxVal) {
//                        maxVal = dp[i - 1][j - k * w[i - 1]] + k * v[i - 1];
//                        maxK = k;
//                    }
//                }
//                dp[i][j] = maxVal;
//                // path存储的是maxVal对应的k的个数
//                path[i][j] = maxK;
//            }
//        }
//
//        // 对dp进行逆向遍历
//        // 跟01背包的遍历很类似
//        int i = path.length - 1;// 表示最后一件物体
//        int j = path[0].length - 1;// 表示背包的最大容量
//        while (i > 0 && j > 0) {
//            // 如果背包的最大容量装入的是最后一件物体
//            if (path[i][j] != 0) {
//                int k = path[i][j];
//                while (k > 0) {
//                    System.out.println("第" + i + "件物品装入背包");
//                    j -= w[i - 1];// 求出剩余的空间
//                    k--;
//                }
//            }
//            // 这里分两种情况：
//            // 1.如果上面的if成立，那么i--是看剩余的空间是否装入了前一件物品
//            // 2.如果上面的if不成立，那么i--是看当前空间是否装入了前一件物品
//            i--;
//        }
//        for (int[] ints : dp) {
//            for (int anInt : ints) {
//                System.out.print(anInt + " ");
//            }
//            System.out.println();
//        }
//        for (int[] ints : path) {
//            for (int anInt : ints) {
//                System.out.print(anInt + " ");
//            }
//            System.out.println();
//        }
    }
}
